{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest String That Contains Three Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #包含三个字符串的最短字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你三个字符串&nbsp;<code>a</code>&nbsp;，<code>b</code>&nbsp;和&nbsp;<code>c</code>&nbsp;， 你的任务是找到长度&nbsp;<strong>最短</strong>&nbsp;的字符串，且这三个字符串都是它的 <strong>子字符串</strong>&nbsp;。\n",
    "<p>如果有多个这样的字符串，请你返回 <strong>字典序最小</strong>&nbsp;的一个。</p>\n",
    "\n",
    "<p>请你返回满足题目要求的字符串。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两个长度相同的字符串 <code>a</code>&nbsp;和 <code>b</code>&nbsp;，如果在第一个不相同的字符处，<code>a</code>&nbsp;的字母在字母表中比 <code>b</code>&nbsp;的字母 <strong>靠前</strong>&nbsp;，那么字符串&nbsp;<code>a</code>&nbsp;比字符串&nbsp;<code>b</code> <strong>字典序小</strong>&nbsp;。</li>\n",
    "\t<li><strong>子字符串</strong>&nbsp;是一个字符串中一段连续的字符序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><code><span style=\"\"><b>输入：</b></span>a</code> = \"abc\", <code>b</code> = \"bca\", <code>c</code> = \"aaa\"\n",
    "<b>输出：</b>\"aaabca\"\n",
    "<b>解释：</b>字符串 \"aaabca\" 包含所有三个字符串：a = ans[2...4] ，b = ans[3..5] ，c = ans[0..2] 。结果字符串的长度至少为 6 ，且\"aaabca\" 是字典序最小的一个。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><code><span style=\"\"><b>输入：</b></span>a</code> = \"ab\", <code>b</code> = \"ba\", <code>c</code> = \"aba\"\n",
    "<b>输出：</b>\"aba\"\n",
    "<strong>解释：</strong>字符串 \"aba\" 包含所有三个字符串：a = ans[0..1] ，b = ans[1..2] ，c = ans[0..2] 。由于 c 的长度为 3 ，结果字符串的长度至少为 3 。\"aba\" 是字典序最小的一个。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= a.length, b.length, c.length &lt;= 100</code></li>\n",
    "\t<li><code>a</code>&nbsp;，<code>b</code>&nbsp;，<code>c</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-string-that-contains-three-strings](https://leetcode.cn/problems/shortest-string-that-contains-three-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-string-that-contains-three-strings](https://leetcode.cn/problems/shortest-string-that-contains-three-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n\"bca\"\\n\"aaa\"', '\"ab\"\\n\"ba\"\\n\"aba\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        results = {self.mergeStr(self.mergeStr(a, b), c), self.mergeStr(self.mergeStr(a, c), b),\n",
    "                   self.mergeStr(self.mergeStr(b, a), c), self.mergeStr(self.mergeStr(b, c), a),\n",
    "                   self.mergeStr(self.mergeStr(c, a), b), self.mergeStr(self.mergeStr(c, b), a)}\n",
    "        min_len = min([len(x) for x in results])\n",
    "        results = [x for x in results if len(x) == min_len]\n",
    "        return sorted(results)[0]\n",
    "\n",
    "    @staticmethod\n",
    "    def mergeStr(head: str, tail: str) -> str:\n",
    "        if head in tail or tail in head:\n",
    "            return head if len(head) > len(tail) else tail\n",
    "        left = 0\n",
    "        right = len(head)\n",
    "        while left < right:\n",
    "            if tail.startswith(head[left: right]):\n",
    "                break\n",
    "            else:\n",
    "                left += 1\n",
    "        return head + tail[right - left:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def join(self, a: str, b: str):\n",
    "        if a in b: return b\n",
    "        if b in a: return a\n",
    "        for i in range(min(len(a), len(b)), 0, -1):\n",
    "            if a[-i:] == b[0:i]:\n",
    "                return a + b[i:]\n",
    "        return a + b\n",
    "\n",
    "\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        ans = a + b + c\n",
    "        for i in permutations([a, b, c]):\n",
    "            s = self.join(self.join(i[0], i[1]), i[2])\n",
    "            if len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "      def merge(s: str, t: str) -> str:\n",
    "        if t in s: return s\n",
    "        if s in t: return t\n",
    "        for i in range(min(len(s), len(t)), 0 , -1):\n",
    "          if s[-i:] == t[:i]:\n",
    "            return s+t[i:]\n",
    "        return s+t\n",
    "      ans = \"\"\n",
    "      for a, b, c in permutations((a, b, c)):\n",
    "        s = merge(merge(a,b),c)\n",
    "        if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "          ans = s\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def f(a,b):\n",
    "            # abbc bb\n",
    "            if a in b: return b\n",
    "            mx=min(len(a),len(b))\n",
    "            for i in range(mx, 0, -1):\n",
    "                if a[-i:]==b[:i]: return a+b[i:]\n",
    "            return a+b\n",
    "        ans=[]\n",
    "        for x,y,z in permutations((a,b,c),3):\n",
    "            ans.append(f(x,f(y,z)))\n",
    "        ans.sort(key=lambda x:(len(x), x))\n",
    "        return ans[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        def sadd(s1,s2):\n",
    "            if s1 in s2:\n",
    "                return s2\n",
    "            if s2 in s1:\n",
    "                return s1\n",
    "            for j in range(min(len(s1),len(s2)),0,-1):\n",
    "                if s1[len(s1)-j:]==s2[:j]:\n",
    "                    return s1+s2[j:]\n",
    "            return s1+s2\n",
    "        \n",
    "        return sorted([sadd(sadd(a,b),c),sadd(sadd(b,a),c),sadd(sadd(a,c),b),sadd(sadd(c,a),b),sadd(sadd(b,c),a),sadd(sadd(c,b),a)],key=lambda x:[len(x),x])[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merage(s, t):\n",
    "            if s in t: return t\n",
    "            if t in s: return s\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merage(merage(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        ans = \"\"\n",
    "\n",
    "        def combine_str(s0, s1):\n",
    "            if s0 in s1: return s1\n",
    "            if s1 in s0: return s0\n",
    "            for i in range(min(len(s0), len(s1)), 0, -1):\n",
    "                if s0[-i:] == s1[:i]:\n",
    "                    return s0 + s1[i:]\n",
    "            return s0 + s1\n",
    "\n",
    "        for a, b, c in permutations([a, b, c]):\n",
    "            s = combine_str(combine_str(a, b), c)\n",
    "            if not ans or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        # 核心思想：贪心\n",
    "        def merge(x,y):\n",
    "            if x in y:return y\n",
    "            if y in x:return x\n",
    "            for i in range(min(len(x),len(y))-1,0,-1):\n",
    "                if x[-i:] == y[:i]:\n",
    "                    return x + y[i:]\n",
    "            return x+y\n",
    "        ans = ''\n",
    "        for x,y,z in permutations((a,b,c)):\n",
    "            s = merge(merge(x,y),z)\n",
    "            if ans == '' or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s:\n",
    "                return s\n",
    "            if s in t:\n",
    "                return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s:str,t:str):\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)),0 , -1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "        \n",
    "        ans = \"\"\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def apply_match_extend(base_str:str, to_match_str:str) -> str:\n",
    "            if base_str.find(to_match_str) >= 0:\n",
    "                return base_str\n",
    "            for j in range(len(to_match_str) - 2, -1, -1):\n",
    "                s = to_match_str[0:j + 1]\n",
    "                if base_str.endswith(s):\n",
    "                    #print(base_str, to_match_str, s)\n",
    "                    return base_str + to_match_str[j + 1:]\n",
    "            return base_str + to_match_str\n",
    "        \n",
    "        min_len, ans = inf, \"\"\n",
    "        # a -> b -> c\n",
    "        for i,j,k in permutations([a,b,c]):\n",
    "            s = apply_match_extend(apply_match_extend(i, j), k)\n",
    "            s_len = len(s)\n",
    "            #print(i, j, k, s, s_len)\n",
    "            if s_len < min_len or (s_len == min_len and s < ans):\n",
    "                min_len = s_len\n",
    "                ans = s\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s,t):\n",
    "            if s in t:\n",
    "                return t \n",
    "            if t in s:\n",
    "                return s \n",
    "            for i in range(min(len(s),len(t)),-1,-1):\n",
    "                if s[len(s)-i:] == t[:i]:\n",
    "                    return s+t[i:]\n",
    "            return s+t \n",
    "        ans = \"\"\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            # 從大到小枚舉重疊長度\n",
    "            # 匹配 s 的後綴與 t 的前綴\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t # 完全不重疊\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def comb(x, y):\n",
    "            for i in range(len(x)):\n",
    "                if y == x[i: i + len(y)]:\n",
    "                    return x\n",
    "                if x[i:] == y[:len(x) - i]:\n",
    "                    return x[:i] + y\n",
    "            return x + y\n",
    "        def c3(x, y, z):\n",
    "            return comb(comb(x, y), z)\n",
    "        s = [c3(a, b, c), c3(a, c, b), c3(b, a, c), c3(b, c, a), c3(c, a, b), c3(c, b, a)]\n",
    "        s.sort(key=lambda x: (len(x), x))\n",
    "        return s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s,t):\n",
    "            if s in t:\n",
    "                return t\n",
    "            if t in s:\n",
    "                return s\n",
    "            for i in range(min(len(s),len(t))-1,0,-1):\n",
    "                if s[-i:]==t[:i]:\n",
    "                    return s+t[i:]\n",
    "            return s+t\n",
    "        ans=a+b+c\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            tmp=merge(merge(a,b),c)\n",
    "            if len(tmp)<len(ans):\n",
    "                ans=tmp\n",
    "            else:\n",
    "                if len(tmp)==len(ans) and tmp<ans:\n",
    "                    ans=tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        \n",
    "        \n",
    "        def inter(A, B):\n",
    "            n, m = len(A), len(B)\n",
    "            \n",
    "            if A.find(B) != -1:\n",
    "                return A\n",
    "            \n",
    "            for i in range(n):\n",
    "                suc = True\n",
    "                k = i\n",
    "                for j in range(m):\n",
    "                    if A[k] != B[j]:\n",
    "                        suc = False\n",
    "                        break\n",
    "                    k += 1\n",
    "                    if k == n:\n",
    "                        break\n",
    "                if suc:\n",
    "                    return A[: i] + B\n",
    "            return A + B\n",
    "\n",
    "        \n",
    "        abc = inter(inter(a, b), c)\n",
    "        acb = inter(inter(a, c), b)\n",
    "        bac = inter(inter(b, a), c)\n",
    "        bca = inter(inter(b, c), a)\n",
    "        cab = inter(inter(c, a), b)\n",
    "        cba = inter(inter(c, b), a)\n",
    "        \n",
    "        res = abc\n",
    "        for s in acb, bac, bca, cab, cba:\n",
    "            if len(res) > len(s):\n",
    "                res = s\n",
    "            elif len(res) == len(s) and res > s:\n",
    "                res = s\n",
    "        \n",
    "        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import itemgetter\n",
    "\n",
    "\n",
    "def concat_string(a: str, b: str) -> str:\n",
    "    if a.find(b) != -1:\n",
    "        return a\n",
    "\n",
    "    if b.find(a) != -1:\n",
    "        return b\n",
    "\n",
    "    for i in range(1, len(b)):\n",
    "        sub = b[:-i]\n",
    "        if a.endswith(sub):\n",
    "            return a + b[-i:]\n",
    "\n",
    "    return a + b  # 两个字符串没有任何重叠时直接拼接\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        # 穷举所有可能拼接\n",
    "        abc = concat_string(concat_string(a, b), c)\n",
    "        acb = concat_string(concat_string(a, c), b)\n",
    "        bac = concat_string(concat_string(b, a), c)\n",
    "        bca = concat_string(concat_string(b, c), a)\n",
    "        cab = concat_string(concat_string(c, a), b)\n",
    "        cba = concat_string(concat_string(c, b), a)\n",
    "\n",
    "        str_list = [[len(abc), abc], [len(acb), acb], [len(bac), bac], [len(bca), bca], [len(cab), cab], [len(cba), cba]]\n",
    "\n",
    "        # 按题目要求进行排序\n",
    "        str_list = sorted(str_list, key=itemgetter(0, 1))\n",
    "\n",
    "        return str_list[0][1]  # 返回排序后的第一个字符串\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s, t):\n",
    "            if s in t: return t\n",
    "            if t in s: return s\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        a,b,c = sorted([a,b,c],key=lambda x:len(x))\n",
    "        if(a in b or a in c):\n",
    "            a = ''\n",
    "        if(b in c):\n",
    "            b = ''\n",
    "        def concatStr(a, b, c):\n",
    "            res1 = a\n",
    "            l = min(len(res1), len(b))\n",
    "            while(l >= 1 and res1[-l:] != b[:l]):\n",
    "                l -= 1\n",
    "            res1 += b[l:]\n",
    "            \n",
    "            l = min(len(res1), len(c))\n",
    "            while(l >= 1 and res1[-l:] != c[:l]):\n",
    "                l -= 1\n",
    "            res1 += c[l:]\n",
    "            l = min(len(b), len(c))\n",
    "            while(l >= 1 and b[-l:] != c[:l]):\n",
    "                l -= 1\n",
    "            res2 = b + c[l:]\n",
    "\n",
    "            l = min(len(a), len(res2))\n",
    "            while(l >= 1 and a[-l:] != res2[:l]):\n",
    "                l -= 1\n",
    "            res2 = a + res2[l:]\n",
    "\n",
    "            if(len(res1) > len(res2)):\n",
    "                return res2\n",
    "            elif(len(res1) < len(res2)):\n",
    "                return res1\n",
    "            else:\n",
    "                return min(res1, res2)\n",
    "\n",
    "        res1 = concatStr(a,b,c)\n",
    "        res2 = concatStr(a,c,b)\n",
    "        res3 = concatStr(b,a,c)\n",
    "        res4 = concatStr(b,c,a)\n",
    "        res5 = concatStr(c,a,b)\n",
    "        res6 = concatStr(c,b,a)\n",
    "        result = []\n",
    "        minLen = float('inf')\n",
    "        for res in [res1, res2, res3, res4, res5, res6]:\n",
    "            if(minLen > len(res)):\n",
    "                minLen = len(res)\n",
    "                result = [res]\n",
    "            elif(minLen == len(res)):\n",
    "                result.append(res)\n",
    "            else:\n",
    "                continue\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(x, y, z):\n",
    "            xy = ''\n",
    "            for index in range(len(x)):\n",
    "                compare_len = min(len(x) - index, len(y))\n",
    "                if x[index: index + compare_len] == y[:compare_len]:\n",
    "                    if compare_len < len(y):\n",
    "                        xy = x[:index] + y\n",
    "                    else:\n",
    "                        xy = x\n",
    "                    break\n",
    "            \n",
    "            if xy == '':\n",
    "                xy = x + y\n",
    "\n",
    "            for index in range(len(xy)):\n",
    "                compare_len = min(len(xy) - index, len(z))\n",
    "                if xy[index: index + compare_len] == z[:compare_len]:\n",
    "                    if compare_len < len(z):\n",
    "                        return xy[:index] + z\n",
    "                    else:\n",
    "                        return xy\n",
    "\n",
    "            return xy + z\n",
    "\n",
    "        candidate = [merge(a, b, c), merge(a, c, b), merge(b, a, c), merge(b, c, a), merge(c, a, b), merge(c, b, a)]\n",
    "        return sorted(candidate, key=lambda d:(len(d), d))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        ans = \"\"\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        # a,b,c的全排列\n",
    "        for a,b,c in set(permutations((a,b,c))):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans==\"\" or len(s)<len(ans) or (len(s)==len(ans) and s<ans):\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def f(x: str, y: str)->str:\n",
    "            if x in y: return y\n",
    "            if y in x: return x\n",
    "            for i in range(min(len(x), len(y)), -1, -1):\n",
    "                if x[-i:] == y[:i]:\n",
    "                    return x[:-i] + y\n",
    "            return x + y\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = f(f(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        def merge(s: str, t: str) -> str:\n",
    "\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "\n",
    "            ts = t+s\n",
    "            nxt = [-1]*len(ts)\n",
    "            for i in range(1, len(ts)):\n",
    "                j = nxt[i-1]\n",
    "                while j >= 0 and (ts[i] != ts[j+1] or j+1 >= len(t)):\n",
    "                    j = nxt[j]\n",
    "                if ts[i] == ts[j+1]:\n",
    "                    nxt[i] = j+1\n",
    "            return s + t[nxt[-1]+1:]\n",
    "        \n",
    "        ans = \"\"\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans == \"\" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        def merge(s, t):\n",
    "            if s in t:\n",
    "                return t\n",
    "            if t in s:\n",
    "                return s\n",
    "            \n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        #难，\n",
    "        #完全没有思路\n",
    "        #暴力嘛\n",
    "        #都不知道怎么暴力\n",
    "\n",
    "        #rwkk是怎么回事\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                # 为什么可以这样枚举\n",
    "                # 这样应该有问题啊\n",
    "                # 1.子字符串不是要连续的吗\n",
    "                # 2.为什么只有首位和末尾？\n",
    "                # 答：子字符串一定是连续的\n",
    "                # 答：因为中间重复的话无法通过添加首位末尾形成一致的，别忘了子字符串是连续的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):#固定只有3*2*1,6种\n",
    "            #print(a,b,c)\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        #难，\n",
    "        #完全没有思路\n",
    "        #暴力嘛\n",
    "        #都不知道怎么暴力\n",
    "\n",
    "        #rwkk是怎么回事\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):#固定只有3*2*1,6种\n",
    "            #print(a,b,c)\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        def connect(a,b):\n",
    "            k = min(len(a), len(b))\n",
    "            if a in b: return b\n",
    "            if b in a: return a\n",
    "            for i in range(k, 0, -1):\n",
    "                if a[-i:] == b[:i]:\n",
    "                    return a + b[i:]\n",
    "            return a+b\n",
    "        \n",
    "        ans = \"\"\n",
    "        for i,j,k in permutations((a, b, c)):\n",
    "            s = connect(connect(i, j), k)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s, t):\n",
    "            if s in t : return t\n",
    "            if t in s: return s\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "        \n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a,b,c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(ans) == len(s) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        def merge(s: str, t: str) -> str:\n",
    "\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "\n",
    "            ts = t+s\n",
    "            nxt = [-1]*len(ts)\n",
    "            for i in range(1, len(ts)):\n",
    "                j = nxt[i-1]\n",
    "                while j >= 0 and (ts[i] != ts[j+1] or j+1 >= len(t)):\n",
    "                    j = nxt[j]\n",
    "                if ts[i] == ts[j+1]:\n",
    "                    nxt[i] = j+1\n",
    "            return s + t[nxt[-1]+1:]\n",
    "        \n",
    "        ans = \"\"\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans == \"\" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        ans = \"\"\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        # a,b,c的全排列\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans==\"\" or len(s)<len(ans) or (len(s)==len(ans) and s<ans):\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        a,b,c = sorted([a,b,c],key=lambda x:len(x))\n",
    "        if(a in b or a in c):\n",
    "            a = ''\n",
    "        if(b in c):\n",
    "            b = ''\n",
    "        def concatStr(a, b, c):\n",
    "            res1 = a\n",
    "            l = min(len(res1), len(b))\n",
    "            while(l >= 1 and res1[-l:] != b[:l]):\n",
    "                l -= 1\n",
    "            res1 += b[l:]\n",
    "            \n",
    "            l = min(len(res1), len(c))\n",
    "            while(l >= 1 and res1[-l:] != c[:l]):\n",
    "                l -= 1\n",
    "            res1 += c[l:]\n",
    "            l = min(len(b), len(c))\n",
    "            while(l >= 1 and b[-l:] != c[:l]):\n",
    "                l -= 1\n",
    "            res2 = b + c[l:]\n",
    "\n",
    "            l = min(len(a), len(res2))\n",
    "            while(l >= 1 and a[-l:] != res2[:l]):\n",
    "                l -= 1\n",
    "            res2 = a + res2[l:]\n",
    "\n",
    "            if(len(res1) > len(res2)):\n",
    "                return res2\n",
    "            elif(len(res1) < len(res2)):\n",
    "                return res1\n",
    "            else:\n",
    "                return min(res1, res2)\n",
    "\n",
    "        res1 = concatStr(a,b,c)\n",
    "        res2 = concatStr(a,c,b)\n",
    "        res3 = concatStr(b,a,c)\n",
    "        res4 = concatStr(b,c,a)\n",
    "        res5 = concatStr(c,a,b)\n",
    "        res6 = concatStr(c,b,a)\n",
    "        result = []\n",
    "        minLen = float('inf')\n",
    "        for res in [res1, res2, res3, res4, res5, res6]:\n",
    "            if(minLen > len(res)):\n",
    "                minLen = len(res)\n",
    "                result = [res]\n",
    "            elif(minLen == len(res)):\n",
    "                result.append(res)\n",
    "            else:\n",
    "                continue\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        @cache\n",
    "        def merge(a, b):\n",
    "            if b in a:\n",
    "                return a\n",
    "            for idx in range(min(len(b), len(a)), 0, -1):\n",
    "        \n",
    "                if a[-idx:] == b[:idx]:\n",
    "                    return a + b[idx:]\n",
    "            return a + b\n",
    "        strs = [a, b, c]\n",
    "        perm = itertools.permutations(range(3))  \n",
    "        res = a + b + c\n",
    "        for p in perm:\n",
    "            temp = merge(strs[p[0]], strs[p[1]])\n",
    "            temp = merge(temp, strs[p[2]])\n",
    "            if len(temp) < len(res) or (len(temp) == len(res) and res > temp):\n",
    "                res =temp\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        # def merge(a, b):\n",
    "        #     if a in b:\n",
    "        #         return b \n",
    "        #     if b in a:\n",
    "        #         return a\n",
    "        #     min_val = min(len(a), len(b))\n",
    "        #     i, j = len(a)-min_val, min_val\n",
    "        #     while i < len(a) and j >= 0 and a[i:] != b[:j]:\n",
    "        #         i += 1\n",
    "        #         j -= 1\n",
    "        #     return a + b[j:] if j < 0 or a[i:] == b[:j] else a + b\n",
    "\n",
    "        # def merge_two(a, b):\n",
    "        #     ab = merge(a, b)\n",
    "        #     ba = merge(b, a)\n",
    "        #     if len(ab) < len(ba):\n",
    "        #         return ab \n",
    "        #     elif len(ab) > len(ba):\n",
    "        #         return ba \n",
    "        #     return ab if ab < ba else ba\n",
    "\n",
    "        # def merge_three(a, b, c):\n",
    "        #     return merge_two(merge_two(a, b), c)\n",
    "        \n",
    "        # abc = merge_three(a, b, c)\n",
    "        # acb = merge_three(a, c, b)\n",
    "        # bca = merge_three(b, c, a)\n",
    "        # if len(abc) == len(acb) == len(bca):\n",
    "        #     return min(abc, acb, bca)\n",
    "        # abc = abc if len(abc) < len(acb) or (len(abc) == len(acb) and abc < acb) else acb \n",
    "        # return abc if len(abc) < len(bca) or (len(abc) == len(bca) and abc < bca) else bca\n",
    "\n",
    "        # ----------------------------------\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        if a in b or a in c:\n",
    "            a = ''\n",
    "        if b in a or b in c:\n",
    "            b = ''\n",
    "        if c in a or c in b:\n",
    "            c = ''\n",
    "        def dfs(a, b):\n",
    "            s = min(len(a), len(b))\n",
    "            for i in range(s, 0, -1):\n",
    "                if a[-i:] == b[:i]:\n",
    "                    return a + b[i: len(b)]\n",
    "            return a + b\n",
    "        st = []\n",
    "        st.append(dfs(dfs(a, b), dfs(b, c)))\n",
    "        st.append(dfs(dfs(a, c), dfs(c, b)))\n",
    "        st.append(dfs(dfs(b, a), dfs(a, c)))\n",
    "        st.append(dfs(dfs(b, c), dfs(c, a)))\n",
    "        st.append(dfs(dfs(c, a), dfs(a, b)))\n",
    "        st.append(dfs(dfs(c, b), dfs(b, a)))\n",
    "        def cmp(a, b):\n",
    "            if len(a) < len(b):\n",
    "                return -1\n",
    "            else:\n",
    "                if len(a) == len(b):\n",
    "                    if a < b:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        return 1\n",
    "                else:\n",
    "                    return 1\n",
    "        st.sort(key = functools.cmp_to_key(cmp))\n",
    "        return st[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def catStr(s1,s2):\n",
    "            l1=len(s1)\n",
    "            l2=len(s2)\n",
    "            p=len(s1)\n",
    "            for i in range(l1):\n",
    "                ok=False\n",
    "                for j in range(i,i+l2):\n",
    "                    if s2[j-i:j-i+1]!=s1[j:j+1]:\n",
    "                        break\n",
    "                    if j==i+l2-1:\n",
    "                        return s1\n",
    "                    if j==l1-1:\n",
    "                        ok=True\n",
    "                        break\n",
    "                if ok:\n",
    "                    p=i\n",
    "                    break\n",
    "            return s1[0:p]+s2\n",
    "        strarr=[]\n",
    "        abc=catStr(catStr(a,b),c)\n",
    "        acb=catStr(catStr(a,c),b)\n",
    "        bac=catStr(catStr(b,a),c)\n",
    "        bca=catStr(catStr(b,c),a)\n",
    "        cab=catStr(catStr(c,a),b)\n",
    "        cba=catStr(catStr(c,b),a)\n",
    "        strarr=[[len(abc),abc],[len(acb),acb],[len(bac),bac],[len(bca),bca],[len(cab),cab],[len(cba),cba]]\n",
    "        strarr=sorted(strarr)\n",
    "        return strarr[0][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s: str, t: str) -> str:\n",
    "            # 先特判完全包含的情况\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                # 枚举：s 的后 i 个字母和 t 的前 i 个字母是一样的\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def help(sb,sp):\n",
    "            if sb in sp:\n",
    "                return sp\n",
    "            if sp in sb:\n",
    "                return sb\n",
    "            x=len(sb)-1\n",
    "            y=0\n",
    "            m=-1\n",
    "            while x>=0 and y<len(sp):\n",
    "                if sb[x:]==sp[:y+1]:\n",
    "                    m=max(m,y)\n",
    "                x-=1\n",
    "                y+=1\n",
    "            return sb+sp[m+1:] if m<len(sp) else sb\n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = help(help(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or len(s) == len(ans) and s < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        a,b,c = sorted([a,b,c],key=lambda x:len(x))\n",
    "        if(a in b or a in c):\n",
    "            a = ''\n",
    "        if(b in c):\n",
    "            b = ''\n",
    "        def concatStr(a, b, c):\n",
    "            res1 = a\n",
    "            l = min(len(res1), len(b))\n",
    "            while(l >= 1 and res1[-l:] != b[:l]):\n",
    "                l -= 1\n",
    "            res1 += b[l:]\n",
    "            \n",
    "            l = min(len(res1), len(c))\n",
    "            while(l >= 1 and res1[-l:] != c[:l]):\n",
    "                l -= 1\n",
    "            res1 += c[l:]\n",
    "            l = min(len(b), len(c))\n",
    "            while(l >= 1 and b[-l:] != c[:l]):\n",
    "                l -= 1\n",
    "            res2 = b + c[l:]\n",
    "\n",
    "            l = min(len(a), len(res2))\n",
    "            while(l >= 1 and a[-l:] != res2[:l]):\n",
    "                l -= 1\n",
    "            res2 = a + res2[l:]\n",
    "\n",
    "            if(len(res1) > len(res2)):\n",
    "                return res2\n",
    "            elif(len(res1) < len(res2)):\n",
    "                return res1\n",
    "            else:\n",
    "                return min(res1, res2)\n",
    "\n",
    "        res1 = concatStr(a,b,c)\n",
    "        res2 = concatStr(a,c,b)\n",
    "        res3 = concatStr(b,a,c)\n",
    "        res4 = concatStr(b,c,a)\n",
    "        res5 = concatStr(c,a,b)\n",
    "        res6 = concatStr(c,b,a)\n",
    "        result = []\n",
    "        minLen = float('inf')\n",
    "        for res in [res1, res2, res3, res4, res5, res6]:\n",
    "            if(minLen > len(res)):\n",
    "                minLen = len(res)\n",
    "                result = [res]\n",
    "            elif(minLen == len(res)):\n",
    "                result.append(res)\n",
    "            else:\n",
    "                continue\n",
    "        return min(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s,t):\n",
    "            if s in t:\n",
    "                return t\n",
    "            if t in s:\n",
    "                return s\n",
    "            for i in range(min(len(s),len(t)),-1,-1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "        \n",
    "        ans = \"\"\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans == \"\" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(a, b):\n",
    "            if a in b:\n",
    "                return b \n",
    "            if b in a:\n",
    "                return a\n",
    "            min_val = min(len(a), len(b))\n",
    "            i, j = len(a)-min_val, min_val\n",
    "            while i < len(a) and j >= 0 and a[i:] != b[:j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            # print(i, j, a[i:], b[:j])\n",
    "            return a + b[j:] if j < 0 or a[i:] == b[:j] else a + b\n",
    "\n",
    "        def merge_two(a, b):\n",
    "            # print('-------')\n",
    "            # print(a, b)\n",
    "            ab = merge(a, b)\n",
    "            ba = merge(b, a)\n",
    "            \n",
    "            # print(ab, ba)\n",
    "            if len(ab) < len(ba):\n",
    "                return ab \n",
    "            elif len(ab) > len(ba):\n",
    "                return ba \n",
    "            return ab if ab < ba else ba\n",
    "\n",
    "        def merge_three(a, b, c):\n",
    "            return merge_two(merge_two(a, b), c)\n",
    "        \n",
    "        abc = merge_three(a, b, c)\n",
    "        acb = merge_three(a, c, b)\n",
    "        bca = merge_three(b, c, a)\n",
    "        # print(abc, acb, bca)\n",
    "        if len(abc) == len(acb) == len(bca):\n",
    "            return min(abc, acb, bca)\n",
    "        abc = abc if len(abc) < len(acb) or (len(abc) == len(acb) and abc < acb) else acb \n",
    "        # print(abc)\n",
    "        return abc if len(abc) < len(bca) or (len(abc) == len(bca) and abc < bca) else bca"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        \n",
    "        def merge(s, t):\n",
    "            if s in t:\n",
    "                return t\n",
    "            if t in s:\n",
    "                return s\n",
    "\n",
    "            for i in range(min(len(s), len(t)), 0, -1):\n",
    "                if s[-i:] == t[:i]:\n",
    "                    return s + t[i:]\n",
    "            return s + t\n",
    "        \n",
    "        ans = \"\"\n",
    "        for a, b, c in permutations((a, b, c)):\n",
    "            s = merge(merge(a, b), c)\n",
    "            if ans == \"\" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def merge(s,t):\n",
    "            if s in t:\n",
    "                return t\n",
    "            if t in s:\n",
    "                return s\n",
    "            for i in range(min(len(s),len(t)),0,-1):\n",
    "                if s[-i:]==t[:i]:\n",
    "                    return s+t[i:]\n",
    "            return s+t\n",
    "        \n",
    "        ans=\"\"\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s=merge(merge(a,b),c)\n",
    "            if ans==\"\" or len(s)<len(ans) or len(s)==len(ans) and s<ans:\n",
    "                ans=s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getMinString(self,s:str,b:str) -> str:\n",
    "        s_len , b_len = len(s),len(b)\n",
    "        max_b_len = 0\n",
    "\n",
    "        if s_len>=b_len:\n",
    "            for i in range(s_len-b_len+1):\n",
    "                if s[i:b_len+i] == b:\n",
    "                    return s\n",
    "\n",
    "\n",
    "        for i in range(1,s_len+1):\n",
    "            if i >b_len:\n",
    "                break\n",
    "            if s[s_len-i:] == b[:i]:\n",
    "                max_b_len = i\n",
    "        \n",
    "        return s+b[max_b_len:]\n",
    "\n",
    "\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        s_ab = self.getMinString(a,b)\n",
    "        s_ac = self.getMinString(a,c)\n",
    "        s_bc = self.getMinString(b,c)\n",
    "        \n",
    "        s_abc = self.getMinString(s_ab,c)\n",
    "    \n",
    "\n",
    "        s_acb = self.getMinString(s_ac,b)        \n",
    "        s_bac = self.getMinString(b,s_ac)\n",
    "        s_bca = self.getMinString(s_bc,a)  \n",
    "\n",
    "        s_cab = self.getMinString(c,s_ab)\n",
    "        s_cba = self.getMinString(self.getMinString(c,b),a)\n",
    "\n",
    "        res = s_abc\n",
    "        arr = [s_acb,s_bac,s_bca,s_cab,s_cba]\n",
    "\n",
    "        for s in arr:\n",
    "            if len(res)>len(s) or (len(res)==len(s) and res>s):\n",
    "                res = s\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def cal(s1, s2):\n",
    "            if s1 in s2:\n",
    "                return s2 \n",
    "            if s2 in s1:\n",
    "                return s1 \n",
    "            for i in range(min(len(s1), len(s2)),0,-1):\n",
    "                if s1[-i:]==s2[:i]:\n",
    "                    return s1+s2[i:]\n",
    "            return s1+s2 \n",
    "        res = \"\"\n",
    "        for x, y, z in permutations((a, b, c)):\n",
    "            s = cal(cal(x, y), z)\n",
    "            print(x,y,z, s)\n",
    "            if res==\"\" or len(s)<len(res) or (len(s)==len(res) and s<res):\n",
    "                res = s \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        def merge(s: str, t: str) -> str:\n",
    "\n",
    "            if t in s: return s\n",
    "            if s in t: return t\n",
    "\n",
    "            ts = t+s\n",
    "            nxt = [-1]*len(ts)\n",
    "            for i in range(1, len(ts)):\n",
    "                j = nxt[i-1]\n",
    "                while j >= 0 and (ts[i] != ts[j+1] or j+1 >= len(t)):\n",
    "                    j = nxt[j]\n",
    "                if ts[i] == ts[j+1]:\n",
    "                    nxt[i] = j+1\n",
    "            print(s)\n",
    "            print(t)\n",
    "            print(nxt)\n",
    "            return s + t[nxt[-1]+1:]\n",
    "        \n",
    "        ans = \"\"\n",
    "        for a,b,c in permutations((a,b,c)):\n",
    "            s = merge(merge(a,b),c)\n",
    "            if ans == \"\" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):\n",
    "                ans = s\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        # s1和s2的最短拼接\n",
    "        def join(s1, s2):\n",
    "            if s2 in s1:\n",
    "                return s1\n",
    "            for l in range(min(len(s1), len(s2)), 0, -1):\n",
    "                if s1[-l:] == s2[:l]:\n",
    "                    return s1 + s2[l:]\n",
    "            return s1 + s2\n",
    "        \n",
    "        # 回溯：已构成的字符串为done，已依次使用三个字符串中的used\n",
    "        def find(done, used):\n",
    "            if len(used) == 3:\n",
    "                nonlocal ans\n",
    "                if len(done) < len(ans) or (len(done) == len(ans) and done < ans):\n",
    "                    ans = done\n",
    "                return\n",
    "            \n",
    "            for i in range(3):\n",
    "                if not used:\n",
    "                    find(s[i], [i])\n",
    "                elif i not in used:\n",
    "                    find(join(done, s[i]), used + [i])\n",
    "        \n",
    "        s = [a, b, c]\n",
    "        ans = a + b + c\n",
    "        find('', [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "\n",
    "        # abc\n",
    "        # acb\n",
    "        # bac\n",
    "        # bca\n",
    "        # cab\n",
    "        # cba\n",
    "\n",
    "        def mer_two_str(x,y):\n",
    "            if y in x:\n",
    "                return x\n",
    "            elif x in y:\n",
    "                return y\n",
    "            max_same_len = 0\n",
    "            min_len = min(len(x), len(y))\n",
    "            for ini in range(1, min_len+1):\n",
    "                if x[-ini:] == y[:ini]:\n",
    "                    max_same_len = ini\n",
    "            \n",
    "            return ''.join([x, y[max_same_len:]])\n",
    "        \n",
    "        print(mer_two_str('abc', 'bca'))\n",
    "\n",
    "        min_len = 1e6\n",
    "        ans = ''\n",
    "        for m,n,x in [(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)]:\n",
    "            for tmp_id in [0,1]:\n",
    "                if tmp_id:\n",
    "                    str_tmp = mer_two_str(mer_two_str(m,n), x)\n",
    "                else:\n",
    "                    str_tmp = mer_two_str(m, mer_two_str(n,x))\n",
    "\n",
    "                if len(str_tmp) < min_len:\n",
    "                    min_len = len(str_tmp)\n",
    "                    ans = str_tmp\n",
    "                elif len(str_tmp) == min_len:\n",
    "                    if str_tmp < ans:\n",
    "                        ans = str_tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        # 返回s1和s2最长公共前后缀长度\n",
    "        def overlap(s1, s2):\n",
    "            for l in range(min(len(s1), len(s2)), -1, -1):\n",
    "                if l == 0 or s1[-l:] == s2[:l]:\n",
    "                    return l\n",
    "        \n",
    "        # 回溯：已构成的字符串为done，已依次使用三个字符串中的used\n",
    "        def find(done, used):\n",
    "            if len(used) == 3:\n",
    "                nonlocal ans\n",
    "                if len(done) < len(ans) or (len(done) == len(ans) and done < ans):\n",
    "                    ans = done\n",
    "                return\n",
    "            \n",
    "            for i in range(3):\n",
    "                if not used:\n",
    "                    find(s[i], [i])\n",
    "                elif i not in used:\n",
    "                    if s[i] in done:\n",
    "                        find(done, used + [i])\n",
    "                    else:\n",
    "                        find(done + s[i][overlap(done, s[i]):], used + [i])\n",
    "        \n",
    "        s = [a, b, c]\n",
    "        ans = a + b + c\n",
    "        find('', [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumString(self, a: str, b: str, c: str) -> str:\n",
    "        def f(s1, s2):\n",
    "            if s2 in s1:\n",
    "                return s1\n",
    "            if s1 in s2:\n",
    "                return s2\n",
    "            for i in range(len(s1)):\n",
    "                if s2.startswith(s1[i:]):\n",
    "                    return s1[:i] + s2\n",
    "            return s1 + s2\n",
    "        \n",
    "        ans = 'z' * 301\n",
    "        for s1, s2, s3 in itertools.permutations([a, b, c]):\n",
    "            s = f(f(s1, s2), s3)\n",
    "            if len(s) < len(ans):\n",
    "                ans = s\n",
    "            elif len(s) == len(ans):\n",
    "                ans = min(ans, s)\n",
    "            print(s1, s2, s3, s)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
